package org.regotto.basics.dataStruct;

/**
 * 双向链表
 */
public class DoubleLinkedList {

    public int[] e = new int[1000];
    public int[] l = new int[1000];
    public int[] r = new int[1000];
    public int idx = 2, m;

    //0表示左端点, 1表示右端点
    public DoubleLinkedList() {
        r[0] = 1;
        l[1] = 0;
    }

    public void I(int k, int x) {
        e[idx] = x; l[idx] = k; r[idx] = r[k]; l[r[k]] = idx; r[k] = idx++;
    }

    public void D(int k) {
        l[r[k]] = l[k];
        r[l[k]] = r[k];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = r[0]; i != 1; i = r[i]) {
            sb.append(e[i]).append(" ");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();
        // R 右端点插入 1
        list.I(list.l[1], 1);
        // L 左端点位置插入2
        list.I(0, 2);
        list.I(0, 3);
        list.I(0, 4);
        System.out.println(list);
        // D
        list.D(0);
        // 在 2 左边插入 5
        list.I(list.l[2 + 1], 5);
        // 在 2 右边插入 6
        list.I(2 + 1, 6);
        System.out.println(list);
    }

}
